package com.LeeCode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 水位上升的泳池中游泳
 */

public class Code778 {
    public static void main(String[] args) {
        int[][] grid = {
                {0, 2},
                {1, 3}
        };
        System.out.println(new Code778().swimInWater(grid));
    }

    // 四个方向：上、右、下、左
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int swimInWater(int[][] grid) {
        int left = -1, right = 2500;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(grid, mid))
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    private boolean check(int[][] grid, int limit) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();

        if (grid[0][0] <= limit) {
            queue.add(new int[]{0, 0});
            visited[0][0] = true;
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            for (int[] dir : DIRECTIONS) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                    if (grid[nr][nc] <= limit) {
                        queue.add(new int[]{nr, nc});
                        visited[nr][nc] = true;
                    }
                }
            }
        }

        return visited[rows - 1][cols - 1];
    }
}
